home *** CD-ROM | disk | FTP | other *** search
/ World of Video / World of Video.iso / gfxprograms / 3dprograms / t3dlib / source / merge.c < prev    next >
C/C++ Source or Header  |  1995-02-13  |  5KB  |  200 lines
  1. /* merge.c - optimize an object by removing common points and edges
  2.  *         - Written by Glenn M. Lewis - 3/10/92
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include "t3dlib.h"
  7. #ifdef __STDC__
  8. #include <stdlib.h>
  9. #include <strings.h>
  10. #include "merge_protos.h"
  11. #endif
  12.  
  13. static char rcs_id[] = "$Id: merge.c,v 1.10 1993/01/30 23:43:03 glewis Exp $";
  14.  
  15. void merge_object();
  16.  
  17. void merge_World(world)
  18. WORLD *world;
  19. {
  20.     OBJECT *o;
  21.  
  22.     for (o=world->object; o; o=o->next)
  23.         merge_object(o);
  24. }
  25.  
  26. void remove_point(desc, p)
  27. register DESC *desc;
  28. int p;
  29. {
  30.     register UWORD *e;
  31.     register int i;
  32.  
  33.     if (p >= desc->pcount-1) {        /* No need to do anything */
  34.         desc->pcount--;
  35.         return;
  36.     }
  37.  
  38.     /* First, move all the points closer to the front of the list */
  39.     bcopy((char*)&desc->pnts[p+1], (char*)&desc->pnts[p],
  40.         (unsigned)(desc->pcount-p-1)*sizeof(XYZ_st));
  41.     desc->pcount--;
  42.     /* Next, decrement all Point indices that are equal to or greater than "p" */
  43.     for (i=desc->ecount,e=desc->edge; i--; e+=2) {
  44.         if (e[0] >= p) e[0]--;
  45.         if (e[1] >= p) e[1]--;
  46.     }
  47. }
  48.  
  49. void remove_edge(desc, e)
  50. register DESC *desc;
  51. int e;
  52. {
  53.     register UWORD *f;
  54.     register int i;
  55.  
  56.     if (e >= desc->ecount-1) {        /* No need to do anything */
  57.         desc->ecount--;
  58.         return;
  59.     }
  60.     /* First, move all the edges closer to the front of the list */
  61.     bcopy((char*)&desc->edge[(e+1)<<1], (char*)&desc->edge[e<<1],
  62.         (unsigned)(desc->ecount-e-1)*2*sizeof(UWORD));
  63.     desc->ecount--;
  64.     /* Next, decrement all Edge indices that are equal to or greater than "e" */
  65.     for (i=desc->fcount,f=desc->face; i--; f+=3) {
  66.         if (f[0] >= e) f[0]--;
  67.         if (f[1] >= e) f[1]--;
  68.         if (f[2] >= e) f[2]--;
  69.     }
  70. }
  71.  
  72. void merge_points(desc, p1, p2)
  73. register DESC *desc;
  74. int p1, p2;
  75. {
  76.     register UWORD *e;
  77.     register int i;
  78.  
  79.     /* First, check all edges, and those that point to "p2" make point to "p1" */
  80.     for (e=desc->edge,i=0; i<desc->ecount; i++,e+=2) {
  81.         if (e[0] == p2) e[0] = p1;
  82.         if (e[1] == p2) e[1] = p1;
  83.         /* If the two points in the edge are the same point, remove the edge! */
  84.         if (e[0] == e[1]) { remove_edge(desc, i); i--; e-=2; }
  85.     }
  86.     /* Next, remove the duplicate point and adjust *all* the pointers */
  87.     remove_point(desc, p2);
  88. }
  89.  
  90. void merge_edges(desc, e1, e2)
  91. register DESC *desc;
  92. int e1, e2;
  93. {
  94.     register UWORD *f;
  95.     register int i;
  96.  
  97.     /* First, check all faces, and those that point to "e2" make point to "e1" */
  98.     for (f=desc->face,i=0; i<desc->fcount; i++,f+=3) {
  99.         if (f[0] == e2) f[0] = e1;
  100.         if (f[1] == e2) f[1] = e1;
  101.         if (f[2] == e2) f[2] = e1;
  102.     }
  103.     /* Next, remove the duplicate edge and adjust *all* the pointers */
  104.     remove_edge(desc, e2);
  105. }
  106.  
  107. void merge_object(obj)
  108. OBJECT *obj;
  109. {
  110.     register DESC *desc;
  111.     XYZ_st *p1, *p2;
  112.     UWORD *e1, *e2;
  113.     register int i, j;
  114.  
  115.     if (obj->child) merge_object(obj->child);
  116.  
  117.     if (!(desc = obj->desc) || !desc->pcount || !desc->ecount) return;
  118.     /* Merge duplicate points */
  119.     /* DO NOT ATTEMPT TO OPTIMIZE THE LOOPS, AS THE VARIABLE REFERENCES *MUST*
  120.      * BE PERFORMED EACH TIME THROUGH THE LOOP SINCE THE STRUCTURE IS CHANGING!
  121.      */
  122.     /* Start at end and work back */
  123.  
  124. #ifdef DEBUG
  125. fprintf(stderr, "Removing unused edges...\n");
  126. #endif
  127.  
  128.     /* Remove unused edges */
  129.     /* Start at end and work back */
  130.     for (i=desc->ecount; i--; ) {
  131. #ifdef DEBUG
  132. fprintf(stderr, "i:%4d:%4d\n", i, desc->ecount);
  133. #endif
  134.         for (j=desc->fcount; j--; ) {
  135.             if (desc->face[3*j]==i ||
  136.                 desc->face[3*j+1]==i ||
  137.                 desc->face[3*j+2]==i) break;    /* Yup, it is used. */
  138.         }
  139.         if (j<0)    /* Edge is not referenced in any face.  Delete. */
  140.             remove_edge(desc, i);
  141.     }
  142.  
  143. #ifdef DEBUG
  144. fprintf(stderr, "Removing unused points...\n");
  145. #endif
  146.  
  147.     for (i=desc->pcount; i--; ) {
  148. #ifdef DEBUG
  149. fprintf(stderr, "i:%4d:%4d\n", i, desc->pcount);
  150. #endif
  151.         for (j=desc->ecount; j--; ) {
  152.             if (desc->edge[j<<1]==i ||
  153.                 desc->edge[(j<<1)+1]==i) break;    /* Yup, it is used. */
  154.         }
  155.         if (j<0)    /* Point is not referenced in any edge.  Delete. */
  156.             remove_point(desc, i);
  157.     }
  158.  
  159. #ifdef DEBUG
  160. fprintf(stderr, "Merging duplicate edges...\n");
  161. #endif
  162.  
  163.     /* Merge duplicate edges */
  164.     /* Start at end and work back */
  165.     for (i=desc->ecount-1; i--; ) {
  166.         e1 = &desc->edge[i<<1];
  167. #ifdef DEBUG
  168. fprintf(stderr, "i:%4d:%4d\n", i, desc->ecount);
  169. #endif
  170.         for (j=i+1; j<desc->ecount; j++) {
  171.             e2 = &desc->edge[j<<1];
  172.             if ((e1[0] == e2[0] && e1[1] == e2[1]) ||
  173.                 (e1[0] == e2[1] && e1[1] == e2[0])) {
  174.                 /* Yep, the edges are identical.  Merge them. */
  175.                 merge_edges(desc, i, j);
  176.                 j--;
  177.             }
  178.         }
  179.     }
  180.  
  181. #ifdef DEBUG
  182. fprintf(stderr, "Merging duplicate points...\n");
  183. #endif
  184.  
  185.     for (i=desc->pcount-1; i--; ) {
  186.         p1 = &desc->pnts[i];
  187. #ifdef DEBUG
  188. fprintf(stderr, "i:%4d:%4d\n", i, desc->pcount);
  189. #endif
  190.         for (j=i+1; j<desc->pcount; j++) {
  191.             p2 = &desc->pnts[j];
  192.             if (p1->x == p2->x && p1->y == p2->y && p1->z == p2->z) {
  193.                 /* Yep, the points are identical.  Merge them. */
  194.                 merge_points(desc, i, j);
  195.                 j--;
  196.             }
  197.         }
  198.     }
  199. }
  200.